class Solution {
public:
    int lengthOfLIS(vector<int>& nums) {
        // dp[i]代表以i位置为结尾的子序列中最长递增子序列的长度
        // 状态转移方程:假设有一个位置j这个下标范围为(0,i)
        // 如果j后面能够加上i那么dp[i] = dp[j]+1,从0到i中选择一个最大的值
        int n = nums.size();
        vector<int> dp(n,1);
        int ret = 0;
        for(int i = 0;i<n;i++)
        {
            int j = 0;
            while(j<i)
            {
                if(nums[j]<nums[i])
                {
                    dp[i] = max(dp[i],dp[j]+1);
                }
                j++;
            }
            ret = max(ret,dp[i]);
        }
        return ret;
    }
};//第一种方法：动态规划解决
class Solution {
public:
    int lengthOfLIS(vector<int>& nums) {
        int n = nums.size();
        vector<int> arr(1,-1111111111111111111);
        for(int i = 0;i<n;i++)
        {
            int tmp = nums[i];
            if(arr[arr.size()-1]<tmp)
            {
                //这个值能够尾插
                arr.push_back(tmp);
                continue;
            }
            //这个值可以二分查找到nums中的右端点
            int left = 0;
            int right = arr.size()-1;
            while(left<right)
            {
                int mid = (left+right)/2;
                if(arr[mid]>tmp)
                {
                    right = mid;
                }
                else if(arr[mid]<tmp)
                {
                    left = mid+1;//去靠经右端点
                }
                else
                {
                    left = mid;
                    break;
                }
            }
            arr[left] = tmp;
        }
        return arr.size()-1;
    }
};//贪心解决